import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;


public class BinaryTree {
	private Node root;
	
	private static class Node{
		Node left;
		Node right;
		int data;
		
		Node(int newdata){
			left = null;
			right = null;
			data = newdata;
		}
	}
	
	public BinaryTree(){
		root = null;
	}

	public void arrayToBinaryTree(int[] arr, int index){
		 root =arrayToBinaryTree(arr, root, index);
	}
	
	
	// Convert array to Binary tree
	public Node arrayToBinaryTree(int[] arr, Node node, int index){
		if(arr.length == 0){
			return null;
		}
		if((index == 0 || arr.length == 1 || node == null)&& index < arr.length){
			node = new Node(arr[index]);
		}
		
		if(index < (arr.length/2)){
			
			 node.left = arrayToBinaryTree(arr, node.left, index*2+1);
			 node.right = arrayToBinaryTree(arr, node.right, index*2+2);
		}
		
		return node;		
		
	}
	
	
	public boolean lookup(int data){
		return lookup(root, data);
	}
	
	public boolean lookup(Node node, int data){
		if(node == null)
			return false;
		
		if(data <= node.data)
			return lookup(node.left, data);
		else
			return lookup(node.right,data);
	}
	
	public void insert(int data){
		root = insert(root, data);
	}
	
	
	public Node insert(Node node, int data){
		if(node == null){
			node = new Node(data);
		}
		else
		{
			if(data <= node.data){
				node.left = insert(node.left, data);
			}
			else
			{
				node.right = insert(node.right,data);
			}
		}
		return node;
	}
	
	
	public int size(){
		return size(root);
	}
	
	public int size(Node node){
		if(node == null) return 0;
		else{
			int l = size(node.left);
			int r = size(node.right);
			return l+1+r;
		}
			
	}
	
	public int maxDepth(){
		return maxDepth(root);
	}
	
	public int maxDepth(Node node){
		if(node == null){
			return 0;
		}
		else
		{
			int l = maxDepth(node.left);
			int r = maxDepth(node.right);
			return (Math.max(l, r)+1);
		}
	}
	
	public void maxDepthNode2(){
		int currentLevel = 1;
		int maxLevel = 0;
		Node deepNode = new Node(0);
		maxDepthNode2(root, currentLevel, maxLevel, deepNode);
		
	}
	
	public void maxDepthNode2(Node node, int currentLevel, int maxLevel, Node deepNode){
		if(node == null){
			return;
		}
		
		if(node.left == null && node.right == null && currentLevel > maxLevel){
			maxLevel = currentLevel;
			deepNode = node;
			System.out.println(maxLevel + " " + deepNode.data);
			return;
		}
		
		maxDepthNode2(node.left, currentLevel + 1, maxLevel, deepNode);
		maxDepthNode2(node.right, currentLevel + 1, maxLevel, deepNode);
	}
	
	public void maxDepthNode(){
		int level = 1;
		HashMap<Integer, Integer> nodeh = new HashMap<Integer, Integer>();
		maxDepthNode(root, level, nodeh);
		int maxKey = MaxNum(nodeh.keySet());
		System.out.println("MaxHeight = " + maxKey+ " " + "node is " + nodeh.get(maxKey));
	}
	
	public void maxDepthNode(Node node, int level, HashMap<Integer, Integer> nodeh){
		if(node == null){
			return;
		}
		if(node.left == null && node.right == null){
			
			nodeh.put(level, node.data);
			System.out.println(node.data + " " + level);
			return;
			
		}
		maxDepthNode(node.left, level + 1, nodeh);
		maxDepthNode(node.right, level + 1, nodeh);
		
		
//		if(maxDepthNode(node.left, level + 1, nodeh)||maxDepthNode(node.right, level + 1, nodeh)){
//			return true;
//		}
//		else{
//			return false;
//		}
		
	}
	
	
	public int MaxNum(Set<Integer> set){
		if(set.size() == 1){
			for(Integer i: set){
				return i;
			}
		}
		if(set.size() == 0){
			return 0;
		}
		int max = 0;
		for(Integer j : set){
			 if(j > max){
				 max = j;
			 }
		}
		
		return max;
	}
	//Find shortest depth
	public int minDepth(){
		return minDepth(root);
	}
	
	public int minDepth(Node node){
		if(node == null){
			return 0;
		}
		else
		{
			int l = maxDepth(node.left);
			int r = maxDepth(node.right);
			return (Math.min(l, r)+1);
		}
		
	}
	
	//Find longestPath in a binary tree
	public void longestPath(){
		int maxHeight = maxDepth();
		int level = 1;
		int[] arr = new int[maxHeight];
	    longestPath(root, maxHeight, level, arr);
	    for(int i = 0; i < arr.length; i++)
	    {
	    	if(i == arr.length-1){
	    		System.out.println(arr[i]);
	    	}
	    	else{
	    	System.out.print(arr[i]+"-->");
	    	}
	    }
	}
	
	public boolean longestPath(Node node, int maxHeight, int level, int[] arr){
		if(node == null){
			return false;
		}
		
		if(level == maxHeight){
			arr[level-1] = node.data;
			return true;
		}
		
		//the array just records only one node data(might be covered), no matter how many nodes existed in the same level.
		arr[level-1] = node.data;
		if(longestPath(node.left, maxHeight, level + 1 , arr) || longestPath(node.right, maxHeight, level + 1, arr)){
			
			return true;
		}
		else{
			return false;
			
		}
	}
	
	public void printTree(){
		printTree(root);
	}
	
	public void printTree(Node node){
		if(node == null){
			return;
		}
		else
		{
			printTree(node.left);
			System.out.print(node.data + "-->");
			printTree(node.right);
			
		}
	}
	
	public void sibling(){
		sibling(root);
	}
	
	
	
	
	//用queue来解决横向遍历的问题，查看queue头元素是否有sibling，有的话把sibling再放进queue中
	public Queue<Integer> sibling(Node node){
		Queue<Node> q = new LinkedList<BinaryTree.Node>();
		Queue<Integer> result = new LinkedList<Integer>();
	    q.add(node);
	    Node current = null;
	    
		while (!q.isEmpty()) {
			current = q.remove();
			result.add(current.data);
			if (current.left != null) {
				q.add(current.left);
			}
			if (current.right != null) {
				q.add(current.right);
			}

		}
		
		System.out.print(result.toString());
		return result;
		
		
	}
	
	public void createSiblingByLevel(){
		createSiblingByLevel(root);
	}
	
	public ArrayList<LinkedList<Node>> createSiblingByLevel(Node node){
		if(node == null){
			return null;
		}
		//Store each level into an ArrayList
		ArrayList<LinkedList<Node>> result =  new ArrayList<LinkedList<Node>>();
		LinkedList<Node> currentLevel = new LinkedList<BinaryTree.Node>();
		
		currentLevel.add(node);
		while(!currentLevel.isEmpty()){
			result.add(currentLevel);
			LinkedList<Node> previousLevel = currentLevel;
			currentLevel = new LinkedList<Node>();
			Iterator<Node> it = previousLevel.iterator();
			while(it.hasNext()){
				Node tempNode = it.next();
				if(tempNode.left != null){
					currentLevel.add(tempNode.left);
				}
				if(tempNode.right != null){
					currentLevel.add(tempNode.right);
				}
			}
			
			
		}
		System.out.println(result.toString());
		return result;
	}
	
	
	public boolean isBlanced(){
		
		return isBlanced(root);
	}
	
	public boolean isBlanced(Node node){
		if(node == null){
			return true;
		}
		
		int difference = maxDepth(node.left) - maxDepth(node.right);
		if(Math.abs(difference) > 1){
			return false;
		}
		else{
			return isBlanced(node.left)&&isBlanced(node.right);
		}
	}
	
	//check whether a binary tree is a Binary Search Tree
	public boolean isBST(){
		return (isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE));
	}
	
	public boolean isBST(Node node, int min, int max){
		
		if(node == null){
			return true;
		}
		else{
			if(node.data > min && node.data < max){
				return (isBST(node.left, min, node.data)&&
						isBST(node.right, node.data, max));
			}
			else{
				return false;
			}
			
		}
		
		
		
		
	}
	
	//打印整个Binarytree的结构
	public int[][] print(){
		int depth = maxDepth(root);// depth of the Binary Tree
		int N = (int) Math.pow(2, depth);// Number of nodes in complete Binary Tree
		int[][] arr = new int[depth][N-1];// Use an 2-dimension array to create the structure
		
		int level = 0; // height control
		
		if(root == null)
		{
			return arr;
		}
	    arr = print(root, level, depth, N/2, arr);
		
		for(int r = 0; r < arr.length; r++){
        	for(int c = 0; c<arr[r].length; c++){
        		
        		if(arr[r][c] == 0){
        			System.out.print(" ");
        		}
        		else{
        			System.out.print(arr[r][c]);
        		}
        		
        	}
        	System.out.println();
        }
		return arr;
	}
	
	public int[][] print(Node node, int level, int depth, int N, int[][] arr){
		
	    if(node != null && level < depth){
			arr[level][N-1] = node.data;
			// if left child exist, height level +1, index becomes previous index - 2 power of depth - 1- 1- level
			print(node.left, level+1, depth , N-(int) Math.pow(2, depth-1-level-1), arr);
			// if left child exist, height level +1, index becomes previous index + 2 power of depth - 1- 1- level
			print(node.right, level+1, depth ,N+(int) Math.pow(2, depth-1-level-1), arr);
		}
		return arr;
	}
	
	
	//Find 2nd largest Node in BST
	public Node find2ndLargest(){
		return find2ndLargest(root);
	}
	
	public Node find2ndLargest(Node node){
		if(node == null){
			return null;
		}
		
		
		
		if(node.right!=null){
			Node next = node.right;
			Node previous = node;
			while(next.right!=null){
				previous = next;
				next = next.right;
			}
			if(next.left==null){
				return previous;
			}
			else{
				return next.left;
			}
			
		}
		else if(node.left != null){
			Node next = node.left;
			
			while(next.right!=null){
				next = next.right;
			}
			
			return next;
			
		}
		
		return node;
		
	}
	
	
	
	public boolean sameTree(Node node1, Node node2){
		//both nodes are empty return true
		if(node1 == null && node2 == null){
			return true;
		}
		else if(node1 != null && node2 != null){
			if(node1.data == node2.data){
				return sameTree(node1.left, node2.left) && sameTree(node1.right, node2.right);
			}
			return false;
		}
		// one node is null another is not return false;
		else{
			return false;
		}
		
	}
	
	public boolean findSum(int num){
		return findSum(root, num);
	}
	
	public boolean findSum(Node node, int sum){
		if(node == null){
			return false;
		}
		if(node.left == null && node.right == null && node.data == sum){
			return true;
		}
		if(findSum(node.left, sum-node.data) || findSum(node.right, sum-node.data)){
			return true;
		}
		else{
			return false;
		}
	}
	
	public ArrayList<Integer> findSumPath(int num){
		ArrayList<Integer> result = new ArrayList<Integer>();
		
		//int[] result = new int[maxDepth()];
		int level = 1;
		if( findSumPath(root, num, level, result)){
			return result;
		}
		else{
			return null;
		}
	}
	
	public boolean findSumPath(Node node, int sum, int level, ArrayList<Integer> result){
		if(node == null){
			return false;
		}
		if((sum - node.data > 0) && (node.left != null || node.right != null )){
			//result[level - 1] = node.data;
			
			result.add(level-1, node.data);
		}
		else if(sum - node.data == 0 && node.left == null && node.right == null){
			//result[level - 1] = node.data;
			result.add(level-1, node.data);
			while (result.size() > level){
				result.remove(level);
			}
			return true;
		}
		if(findSumPath(node.left, sum-node.data, level + 1, result) 
			|| findSumPath(node.right, sum-node.data, level + 1, result)){
			return true;
		}
		else{
			return false;
		}
	}
	
	
	public ArrayList<ArrayList<Integer>> findMultipleSumPath(int num ){
			ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		
			//int[] result = new int[maxDepth()];
			int level = 1;
			return findMultipleSumPath(root, num, level, new ArrayList<Integer>(), result);
				
	}
	
	public ArrayList<ArrayList<Integer>> findMultipleSumPath(Node node, int sum, int level, ArrayList<Integer> temp, ArrayList<ArrayList<Integer>> result ){
		if(node == null){
			return null;
		}
		if((sum - node.data > 0) && (node.left != null || node.right != null) ){
			temp.add(level - 1, node.data);
		}
		else if(sum - node.data == 0 && node.left == null && node.right == null){
			temp.add(level - 1, node.data);
			while (temp.size() > level){
				temp.remove(level);
			}
			
			ArrayList<Integer> previous = (ArrayList<Integer>) temp.clone();
			
			result.add(previous);
			
		}
		
		
		
		findMultipleSumPath(node.left, sum - node.data, level + 1, temp, result);
		findMultipleSumPath(node.right, sum - node.data, level + 1, temp, result);
		
		return result;
	}
	
	
	
	
	public static void main(String args[]){
		BinaryTree bt = new BinaryTree();
		//Node node = new Node(0);
		bt.insert(6);
		bt.insert(4);
		bt.insert(8);
		bt.insert(3);
		bt.insert(5);
		bt.insert(7);
		bt.insert(9);
		bt.insert(10);
		System.out.println(bt.isBlanced());
		System.out.println(bt.size());
		bt.maxDepthNode();
		bt.maxDepthNode2();
		bt.print();
		System.out.println(bt.findSum(15));
		//int[] result = bt.findSumPath(33);
		ArrayList<Integer> result = bt.findSumPath(33);
		
		for(Integer NodeData : result){
			System.out.print(NodeData + "-->");
		}
		
		bt.findMultipleSumPath(33);
		
		System.out.println();
		bt.createSiblingByLevel();
//		System.out.println(bt.minDepth());
		bt.longestPath();
		bt.printTree();
		System.out.println();
		System.out.println("The 2nd largest node in BST is " + bt.find2ndLargest().data);
		bt.sibling();
		//System.out.print(Integer.MIN_VALUE);
		System.out.println(bt.isBST());
		
		BinaryTree bt2 = new BinaryTree();
		
		//int [] arr = {1,2,3,4,5,6,7,8};
		int [] arr = {5, 4, 8, 11, 13, 4, 12, 2, 5, 1};
        bt2.arrayToBinaryTree(arr, 0);
        
        bt2.printTree();
       
        System.out.println();
        bt2.print();
        System.out.println(bt2.findMultipleSumPath(25));
	}
}
